
public class BinaryFind_hjl {

    public static void main(String[] args) {
        int[] array = {-4, 1, 2, 2, 5, 5, 5, 8, 10};
        int target = 8;
        int lastLEPosition = findLastLE(array, target);
        System.out.println(lastLEPosition >= 0 ? ("最后一个小于等于" + target + "的数是: " + array[lastLEPosition]) : "没找到");

        int firstGEPosition = findFirstG(array, target);
        System.out.println(firstGEPosition >= 0 ? ("第一个大于" + target + "的数是: " + array[firstGEPosition]) : "没找到");

        lastLEPosition = firstGEPosition < 0 ? firstGEPosition : (firstGEPosition - 1);
        System.out.print(lastLEPosition >= 0 ? ("通过找到第一个大于" + target + "的数的方案找到最后一个小于等于" + target + "的数为 " + array[lastLEPosition]) : "没找到");
    }

    /**
     * 找最后一个小于等于的
     *
     * @param array
     * @param target
     * @return
     */
    private static int findLastLE(int[] array, int target) {
        int n = array.length;
        int start = 0;
        int end = n - 1;
        while (start <= end) {
            int mid = (start + end) >> 1;
            if (array[mid] <= target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        if (start == 0) {
            return -1;
        }
        return start - 1;
    }

    /**
     * 找第一个大于的
     *
     * @param array
     * @param target
     * @return
     */
    private static int findFirstG(int[] array, int target) {
        int n = array.length;
        int start = 0;
        int end = n - 1;
        while (start <= end) {
            int mid = (start + end) >> 1;
            if (array[mid] <= target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        if (end == n - 1) {
            return -1;
        }
        return end + 1;
    }
}
